use std::cell::RefMut;
use std::cmp::{Eq, PartialEq};
use std::collections::{HashMap, HashSet, VecDeque};
use std::fmt::Display;
use std::hash::{Hash, Hasher};
use std::ops::{Deref, DerefMut};
use std::{cell::RefCell, rc::Rc};

struct TreeLink(Option<Rc<RefCell<TreeNode>>>);
impl Deref for TreeLink {
    type Target = Option<Rc<RefCell<TreeNode>>>;
    fn deref(&self) -> &Self::Target {
        &self.0
    }
}
impl DerefMut for TreeLink {
    fn deref_mut(&mut self) -> &mut Self::Target {
        &mut self.0
    }
}
impl Clone for TreeLink {
    fn clone(&self) -> Self {
        TreeLink(self.as_ref().map(|node| node.clone()))
    }
}
impl Eq for TreeLink {}
impl PartialEq for TreeLink {
    fn eq(&self, other: &Self) -> bool {
        let lp = self.as_deref().map(|node| node.as_ptr());
        let rp = other.as_deref().map(|node| node.as_ptr());
        lp == rp
    }
}
impl Hash for TreeLink {
    fn hash<H>(&self, state: &mut H)
    where
        H: Hasher,
    {
        if self.is_none() {
            0.hash(state);
        } else {
            self.as_ref().map(|node| node.as_ptr().hash(state));
        }
    }
}

impl TreeLink {
    fn new(node: TreeNode) -> Self {
        Self(Some(Rc::new(RefCell::new(node))))
    }

    fn node(&self) -> &Rc<RefCell<TreeNode>> {
        self.as_ref().unwrap()
    }
    fn inner_mut(&self) -> RefMut<TreeNode> {
        self.as_ref().unwrap().borrow_mut()
    }

    fn elem(&self) -> i32 {
        self.as_ref().unwrap().borrow().elem
    }

    fn left(&self) -> Self {
        self.as_ref()
            .map_or(TreeLink(None), |node| node.borrow().left.clone())
    }
    fn right(&self) -> Self {
        self.as_ref()
            .map_or(TreeLink(None), |node| node.borrow().right.clone())
    }

    fn is_cbt(&self) -> bool {
        let mut queue: VecDeque<TreeLink> = VecDeque::new();
        let head = TreeLink(Some(self.as_ref().unwrap().clone()));
        queue.push_front(head);
        let mut leaf = false;

        while let Some(node) = queue.pop_back() {
            if node.is_none() {
                break;
            }
            if node.left().is_none() && node.right().is_some() {
                return false;
            }
            if node.left().is_some() && node.right().is_none() {
                leaf = true;
            }
            if leaf && node.left().is_some() {
                return false;
            }

            if node.left().is_some() {
                queue.push_front(node.left());
            }
            if node.right().is_some() {
                queue.push_front(node.right());
            }
        }

        true
    }

    fn is_bts(&self) -> bool {
        TreeLink::check_bts(self).is_sbt
    }

    fn check_bts(tree: &TreeLink) -> SbtInfo {
        if tree.is_none() {
            return SbtInfo::new(true);
        }

        let elem = tree.elem();
        let left = TreeLink::check_bts(&tree.left());
        if !left.is_sbt || elem <= left.max_value {
            return SbtInfo::new(false);
        }

        let right = TreeLink::check_bts(&tree.right());
        if !right.is_sbt || elem >= right.min_value {
            return SbtInfo::new(false);
        }

        SbtInfo {
            is_sbt: true,
            max_value: elem.max(right.max_value),
            min_value: elem.min(left.min_value),
        }
    }

    fn max_width(&self) -> usize {
        if self.is_none() {
            return 0;
        }

        let mut max_level_nodes = 0;
        let mut cur_level_nodes = 0;
        let mut stack: VecDeque<TreeLink> = VecDeque::new();
        let head = TreeLink(Some(self.as_ref().unwrap().clone()));
        stack.push_front(head.clone());
        let mut cur_end = head.clone();
        let mut next_end = head;

        while let Some(node) = stack.pop_back() {
            cur_level_nodes += 1;
            if node.left().is_some() {
                stack.push_front(node.left().clone());
                next_end = node.left().clone();
            }
            if node.right().is_some() {
                stack.push_front(node.right().clone());
                next_end = node.right().clone();
            }

            if node == cur_end {
                max_level_nodes = max_level_nodes.max(cur_level_nodes);
                cur_level_nodes = 0;
                cur_end = next_end.clone();
            }
        }

        max_level_nodes.max(cur_level_nodes)
    }

    fn max_width_hashmap(&self) -> usize {
        if self.is_none() {
            return 0;
        }

        let mut map: HashMap<TreeLink, usize> = HashMap::new();
        let mut max_level_nodes = 0;
        let mut cur_level_nodes = 0;
        let mut curlevel = 1;
        let mut stack: VecDeque<TreeLink> = VecDeque::new();
        let head = TreeLink(Some(self.as_ref().unwrap().clone()));
        stack.push_front(head.clone());
        map.insert(head, curlevel);

        while let Some(node) = stack.pop_back() {
            if node.is_none() {
                break;
            }
            let node_level = *map.get(&node).unwrap();

            if node_level == curlevel {
                cur_level_nodes += 1;
            } else {
                curlevel += 1;
                cur_level_nodes = 1;
                max_level_nodes = max_level_nodes.max(cur_level_nodes);
            }

            if node.left().is_some() {
                stack.push_front(node.left());
                map.insert(node.left(), curlevel + 1);
            }
            if node.right().is_some() {
                stack.push_front(node.right());
                map.insert(node.right(), curlevel + 1);
            }
        }

        max_level_nodes.max(cur_level_nodes)
    }

    fn get_fbt_info(tree: &TreeLink) -> FbtInfo {
        if tree.is_none() {
            return FbtInfo { deep: 0, nodes: 0 };
        }

        let left = TreeLink::get_fbt_info(&tree.left());
        let right = TreeLink::get_fbt_info(&tree.right());

        FbtInfo {
            deep: left.deep.max(right.deep) + 1,
            nodes: left.nodes + right.nodes + 1,
        }
    }

    fn is_fbt_cursive(&self) -> bool {
        let info = TreeLink::get_fbt_info(self);
        (1 << info.deep) - 1 == info.nodes
    }

    fn is_fbt(&self) -> bool {
        if self.is_none() {
            return true;
        }

        let mut deep = 0;
        let mut nodes = 0;
        let mut next_end = TreeLink(None);
        let mut queue: VecDeque<TreeLink> = VecDeque::new();
        let head = self.as_ref().unwrap().clone();
        let mut cur_end = TreeLink(Some(head.clone()));
        queue.push_front(TreeLink(Some(head)));

        while let Some(tree) = queue.pop_back() {
            if tree.is_none() {
                break;
            }
            nodes += 1;
            if tree.left().is_some() {
                queue.push_front(tree.left());
                next_end = tree.left();
            }
            if tree.right().is_some() {
                queue.push_front(tree.right());
                next_end = tree.right();
            }

            if tree == cur_end {
                deep += 1;
                cur_end = TreeLink(next_end.0.take());
            }
        }

        (1 << deep) - 1 == nodes
    }

    fn get_bbt_info(tree: &TreeLink) -> BbtInfo {
        if tree.is_none() {
            return BbtInfo {
                is_bbt: true,
                deep: 0,
            };
        }

        let left = TreeLink::get_bbt_info(&tree.left());
        let right = TreeLink::get_bbt_info(&tree.right());

        BbtInfo {
            is_bbt: left.is_bbt && right.is_bbt && (left.deep - right.deep).abs() < 2,
            deep: left.deep.max(right.deep) + 1,
        }
    }

    fn is_bbt(&self) -> bool {
        TreeLink::get_bbt_info(self).is_bbt
    }
}

struct SbtInfo {
    is_sbt: bool,
    max_value: i32,
    min_value: i32,
}
impl SbtInfo {
    fn new(is_bts: bool) -> SbtInfo {
        Self {
            is_sbt: is_bts,
            max_value: i32::MIN,
            min_value: i32::MAX,
        }
    }
}

struct FbtInfo {
    deep: u32,
    nodes: usize,
}

struct BbtInfo {
    is_bbt: bool,
    deep: i32,
}

impl Display for TreeLink {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        if self.is_none() {
            write!(f, "None")?;
            return Ok(());
        }

        self.0
            .as_ref()
            .map(|node| write!(f, "[{} -> ]", node.borrow().elem).unwrap());

        Ok(())
    }
}

struct TreeNode {
    elem: i32,
    left: TreeLink,
    right: TreeLink,
}
impl TreeNode {
    fn new(elem: i32) -> Self {
        Self {
            elem,
            left: TreeLink(None),
            right: TreeLink(None),
        }
    }
}

fn create_bitree(vnodes: &mut VecDeque<&str>) -> TreeLink {
    if let Some(elem) = vnodes.pop_front() {
        if elem == "N" {
            return TreeLink(None);
        }

        let mut node = TreeNode::new(elem.parse::<i32>().unwrap());

        node.left = create_bitree(vnodes);
        node.right = create_bitree(vnodes);
        return TreeLink::new(node);
    }

    TreeLink(None)
}

fn preorder_cursive(tree: &TreeLink, v: &mut Vec<i32>) {
    if let Some(node) = tree.as_ref() {
        v.push(node.borrow().elem);
        preorder_cursive(&node.borrow().left, v);
        preorder_cursive(&node.borrow().right, v);
    }
}

fn preorder(tree: &TreeLink, v: &mut Vec<i32>) {
    if tree.is_none() {
        return;
    }

    let mut stack: Vec<TreeLink> = vec![];
    stack.push(tree.clone());
    while let Some(tree) = stack.pop() {
        if let Some(node) = tree.as_ref() {
            v.push(node.borrow().elem);
            stack.push(node.borrow().right.clone());
            stack.push(node.borrow().left.clone());
        }
    }
}

fn postorder_cursive(tree: &TreeLink, v: &mut Vec<i32>) {
    if let Some(node) = tree.as_ref() {
        postorder_cursive(&node.borrow().left, v);
        postorder_cursive(&node.borrow().right, v);
        v.push(node.borrow().elem);
    }
}

fn postorder(tree: &TreeLink, v: &mut Vec<i32>) {
    if tree.is_none() {
        return;
    }

    let mut stack: Vec<TreeLink> = vec![];
    let mut help: Vec<TreeLink> = vec![];
    stack.push(tree.clone());
    while let Some(tree) = stack.pop() {
        help.push(tree.clone());
        if let Some(node) = tree.as_ref() {
            stack.push(node.borrow().left.clone());
            stack.push(node.borrow().right.clone());
        }
    }

    while let Some(tree) = help.pop() {
        if let Some(node) = tree.as_ref() {
            v.push(node.borrow().elem);
        }
    }
}

fn push_left(tree: &TreeLink, stack: &mut Vec<TreeLink>) {
    let mut left = tree.clone();
    while let Some(node) = left.0 {
        stack.push(TreeLink(Some(node.clone())));
        left = node.borrow().left.clone();
    }
}

fn midorder_cursive(tree: &TreeLink, v: &mut Vec<i32>) {
    if let Some(node) = tree.as_ref() {
        midorder_cursive(&node.borrow().left, v);
        v.push(node.borrow().elem);
        midorder_cursive(&node.borrow().right, v);
    }
}

fn midorder(tree: &TreeLink, v: &mut Vec<i32>) {
    if tree.is_none() {
        return;
    }

    let mut stack = Vec::new();
    push_left(tree, &mut stack);

    while let Some(tree) = stack.pop() {
        if let Some(node) = tree.as_ref() {
            v.push(node.borrow().elem);
            push_left(&node.borrow().right, &mut stack);
        }
    }
}

fn width_traversial(tree: &TreeLink, v: &mut Vec<i32>) {
    let mut queue: VecDeque<TreeLink> = VecDeque::new();
    queue.push_front(tree.clone());
    while let Some(tree) = queue.pop_back() {
        if let Some(node) = tree.as_ref() {
            v.push(node.borrow().elem);
            queue.push_front(node.borrow().left.clone());
            queue.push_front(node.borrow().right.clone());
        }
    }
}

fn create_parentmap(tree: &TreeLink, map: &mut HashMap<TreeLink, TreeLink>) {
    if tree.is_none() {
        return;
    }

    let node = tree.as_ref().unwrap();
    if tree.left().is_some() {
        map.insert(tree.left(), TreeLink(Some(node.clone())));
        create_parentmap(&tree.left(), map);
    }
    if tree.right().is_some() {
        map.insert(tree.right(), TreeLink(Some(node.clone())));
        create_parentmap(&tree.right(), map);
    }
}

fn find_lca(tree: &TreeLink, n1: &TreeLink, n2: &TreeLink) -> TreeLink {
    if tree.is_none() || n1.is_none() || n2.is_none() {
        return tree.clone();
    }

    let root = TreeLink(Some(tree.node().clone()));

    let mut parentmap: HashMap<TreeLink, TreeLink> = HashMap::new();
    create_parentmap(tree, &mut parentmap);
    parentmap.insert(root.clone(), root.clone());
    let mut set: HashSet<TreeLink> = HashSet::new();
    set.insert(root.clone());
    let mut parent = TreeLink(Some(n1.node().clone()));

    while root != parent {
        set.insert(TreeLink(Some(parent.node().clone())));
        let n = TreeLink(Some(parent.node().clone()));
        parent = TreeLink(Some(parentmap.get(&n).unwrap().node().clone()));
    }

    parent = TreeLink(Some(n2.node().clone()));
    while root != parent {
        if set.contains(&parent) {
            return parent;
        }
        let n = TreeLink(Some(parent.node().clone()));
        parent = TreeLink(Some(parentmap.get(&n).unwrap().node().clone()));
    }

    root
}

fn find_node(tree: &TreeLink, elem: i32) -> TreeLink {
    if tree.is_none() {
        return TreeLink(None);
    }
    if tree.node().borrow().elem == elem {
        return TreeLink(Some(tree.node().clone()));
    }

    let l = find_node(&tree.left(), elem);
    let r = find_node(&tree.right(), elem);
    if l.is_some() {
        return l;
    }
    if r.is_some() {
        return r;
    }

    TreeLink(None)
}

fn find_lca_cursive(tree: &TreeLink, n1: &TreeLink, n2: &TreeLink) -> TreeLink {
    if tree.is_none() || n1 == tree || n2 == tree {
        return tree.clone();
    }

    let o1 = find_lca_cursive(&tree.left(), n1, n2);
    let o2 = find_lca_cursive(&tree.right(), n1, n2);

    match (&o1, &o2) {
        (TreeLink(None), TreeLink(None)) => TreeLink(None),
        (TreeLink(Some(_)), TreeLink(None)) => o1.clone(),
        (TreeLink(None), TreeLink(Some(_))) => o2.clone(),
        (TreeLink(Some(_)), TreeLink(Some(_))) => tree.clone(),
    }
}

struct Node3 {
    elem: i32,
    left: Node3Link,
    right: Node3Link,
    parent: Node3Link,
}
impl Node3 {
    fn new(elem: i32) -> Self {
        Self {
            elem,
            left: Node3Link(None),
            right: Node3Link(None),
            parent: Node3Link(None),
        }
    }
}

struct Node3Link(Option<Rc<RefCell<Node3>>>);
impl Deref for Node3Link {
    type Target = Option<Rc<RefCell<Node3>>>;
    fn deref(&self) -> &Self::Target {
        &self.0
    }
}
impl Eq for Node3Link {}
impl PartialEq for Node3Link {
    fn eq(&self, other: &Self) -> bool {
        let lp = self.as_deref().map(|node| node.as_ptr());
        let rp = other.as_deref().map(|node| node.as_ptr());
        lp == rp
    }
}
impl Display for Node3Link {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        if self.is_none() {
            write!(f, "None")?;
            return Ok(());
        }

        self.0
            .as_ref()
            .map(|node| write!(f, "[{} -> ]", node.borrow().elem).unwrap());

        Ok(())
    }
}

impl Node3Link {
    fn node(&self) -> &Rc<RefCell<Node3>> {
        self.as_ref().unwrap()
    }

    fn left(&self) -> Self {
        self.as_ref()
            .map_or(Node3Link(None), |node| node.borrow().left.clone())
    }
    fn right(&self) -> Self {
        self.as_ref()
            .map_or(Node3Link(None), |node| node.borrow().right.clone())
    }

    fn midorder_cursive(tree: &Node3Link) {
        if tree.is_none() {
            return;
        }

        Node3Link::midorder_cursive(&tree.as_ref().unwrap().borrow().left.clone());
        tree.as_ref().map(|node| {
            println!(
                "(node: {}, parent: {}) ",
                node.borrow().elem,
                node.borrow().parent.as_ref().unwrap().borrow().elem
            );
        });
        Node3Link::midorder_cursive(&tree.as_ref().unwrap().borrow().right.clone());
    }

    fn preorder_cursive(tree: &Node3Link) {
        if tree.is_none() {
            return;
        }

        tree.as_ref().map(|node| {
            println!(
                "node: {}, parent: {}",
                node.borrow().elem,
                node.borrow().parent.as_ref().unwrap().borrow().elem
            );
        });

        Node3Link::preorder_cursive(&tree.as_ref().unwrap().borrow().left.clone());
        Node3Link::preorder_cursive(&tree.as_ref().unwrap().borrow().right.clone());
    }

    fn left_edge_leaf(mut node: Node3Link) -> Node3Link {
        while let Some(left) = node.0 {
            if left.borrow().left.is_none() {
                return Node3Link(Some(left));
            }
            node = left.borrow().left.clone();
        }

        Node3Link(None)
    }

    fn find_node_successor(&self, node: &Node3Link) -> Node3Link {
        if self.is_none() || node.is_none() {
            return Node3Link(None);
        }
        let mut node = Node3Link(Some(node.as_ref().unwrap().clone()));

        if node.node().borrow().right.is_some() {
            return Node3Link::left_edge_leaf(node.node().borrow().right.clone());
        }

        let mut parent = node.node().borrow().parent.clone();
        while parent.is_some() && parent.node().borrow().left.clone() != node {
            node = parent.clone();
            let p = parent.node().borrow().parent.clone();
            parent = p;

            // 如果是根节点
            if node == parent {
                return Node3Link(None);
            }
        }

        return node.node().borrow().parent.clone();
    }

    fn find_node3(tree: &Node3Link, elem: i32) -> Node3Link {
        if tree.is_none() {
            return Node3Link(None);
        }
        if tree.node().borrow().elem == elem {
            return Node3Link(Some(tree.node().clone()));
        }

        let l = Node3Link::find_node3(&tree.left(), elem);
        let r = Node3Link::find_node3(&tree.right(), elem);
        if l.is_some() {
            return l;
        }
        if r.is_some() {
            return r;
        }

        Node3Link(None)
    }
}
impl Clone for Node3Link {
    fn clone(&self) -> Self {
        Node3Link(self.as_ref().map(|node| node.clone()))
    }
}

fn create_node3tree(vnodes: &mut VecDeque<&str>, parent: &Node3Link) -> Node3Link {
    if let Some(elem) = vnodes.pop_front() {
        if elem == "N" {
            return Node3Link(None);
        }

        let node = Rc::new(RefCell::new(Node3::new(elem.parse::<i32>().unwrap())));
        node.borrow_mut().parent = if parent.is_none() {
            Node3Link(Some(node.clone()))
        } else {
            Node3Link(Some(parent.as_ref().unwrap().clone()))
        };
        let parent = Node3Link(Some(node.clone()));

        node.borrow_mut().left = create_node3tree(vnodes, &parent);
        node.borrow_mut().right = create_node3tree(vnodes, &parent);
        return parent;
    }

    Node3Link(None)
}

struct MaxDistInfo {
    deep: usize,
    max_dist: usize,
}
impl MaxDistInfo {
    fn new(deep: usize, max_dist: usize) -> Self {
        Self { deep, max_dist }
    }
}

fn max_distance_in_tree(tree: &TreeLink) -> MaxDistInfo {
    if tree.is_none() {
        return MaxDistInfo::new(0, 0);
    }

    let left = max_distance_in_tree(&tree.left());
    let right = max_distance_in_tree(&tree.right());
    // 可能1：最大路径在左树或右树上
    let p1 = left.max_dist;
    let p2 = right.max_dist;
    // 可能2：最大路径经过当前tree节点，这个路径长度就是p3
    let p3 = left.deep + right.deep + 1;
    // 取可能1和可能2的最大值
    let max_dist = p1.max(p2.max(p3));
    // 当前节点tree的最大深度，这是为填充MaxDistInfo准备的，给上层决策用
    let deep = left.deep.max(right.deep) + 1;

    MaxDistInfo::new(deep, max_dist)
}

fn test_distance_in_tree(tree: &TreeLink) -> usize {
    max_distance_in_tree(tree).max_dist
}

fn morris_pre(tree: &TreeLink) {
    print!(">>> morris 前序遍历：");
    if tree.is_none() {
        return;
    }

    let mut cur = tree.clone();
    let mut most_right: TreeLink;

    while cur.is_some() {
        most_right = cur.left();
        if most_right.is_some() {
            while most_right.right().is_some() && most_right.right() != cur {
                most_right = most_right.right();
            }

            if most_right.right().is_none() {
                print!("{}", cur);
                most_right.inner_mut().right = cur.clone();
                cur = cur.left();
                continue;
            } else {
                most_right.inner_mut().right = TreeLink(None);
            }
        } else {
            print!("{}", cur);
        }
        cur = cur.right();
    }
    println!();
}

fn morris_mid(tree: &TreeLink) {
    print!(">>> morris 中序遍历：");
    if tree.is_none() {
        return;
    }

    let mut cur = tree.clone();
    let mut most_right: TreeLink;

    while cur.is_some() {
        most_right = cur.left();
        if most_right.is_some() {
            while most_right.right().is_some() && most_right.right() != cur {
                most_right = most_right.right();
            }

            if most_right.right().is_none() {
                most_right.inner_mut().right = cur.clone();
                cur = cur.left();
                continue;
            } else {
                print!("{}", most_right.right());
                most_right.inner_mut().right = TreeLink(None);
            }
        } else {
            print!("{}", cur);
        }
        cur = cur.right();
    }
    println!();
}

fn rev_edge(tree: &TreeLink) -> TreeLink {
    let mut prev: TreeLink = TreeLink(None);
    let mut cur = tree.clone();
    let mut next: TreeLink;

    while cur.is_some() {
        next = cur.right();
        cur.inner_mut().right = prev;
        prev = cur;
        cur = next;
    }
    prev
}

fn rev_print_right_edge(tree: &TreeLink) {
    if tree.right().is_none() {
        print!("{}", tree);
        return;
    }
    let mut cur = rev_edge(tree);
    let tail = cur.clone();

    while cur.is_some() {
        print!("{}", cur);
        cur = cur.right();
    }

    rev_edge(&tail);
}

fn morris_post(tree: &TreeLink) {
    print!(">>> morris 后序遍历：");
    if tree.is_none() {
        return;
    }

    let mut cur = tree.clone();
    let mut most_right: TreeLink;

    while cur.is_some() {
        most_right = cur.left();
        if most_right.is_some() {
            while most_right.right().is_some() && most_right.right() != cur {
                most_right = most_right.right();
            }

            if most_right.right().is_none() {
                most_right.inner_mut().right = cur.clone();
                cur = cur.left();
                continue;
            } else {
                most_right.inner_mut().right = TreeLink(None);
                rev_print_right_edge(&cur.left());
            }
        }
        cur = cur.right();
    }
    rev_print_right_edge(tree);
    println!()
}

pub fn bitree_main() {
    let mut vnodes: VecDeque<&str> = "1_2_4_N_N_5_N_N_3_6_N_N_7_N_N".split("_").collect();
    let tree = create_bitree(&mut vnodes);
    let mut v = vec![];
    preorder_cursive(&tree, &mut v);
    println!("先序遍历[递归]：{:?}", v);
    v.clear();
    preorder(&tree, &mut v);
    println!("先序遍历：{:?}", v);
    v.clear();
    midorder(&tree, &mut v);
    println!("中序遍历：{:?}", v);
    v.clear();
    midorder_cursive(&tree, &mut v);
    println!("中序遍历[递归]：{:?}", v);
    v.clear();
    postorder(&tree, &mut v);
    println!("后序遍历：{:?}", v);
    v.clear();
    postorder_cursive(&tree, &mut v);
    println!("后序遍历[递归]：{:?}", v);
    v.clear();
    width_traversial(&tree, &mut v);
    println!("宽度遍历：{:?}", v);
    println!("最大层节点数：{}", tree.max_width());
    println!("最大层节点数[hash]：{}", tree.max_width_hashmap());

    let tree = "1_2_4_N_N_5_N_N_3_6_N_N_7_N_N";
    println!("\ntree: {:?}", tree);
    let mut vnodes: VecDeque<&str> = tree.split("_").collect();
    let tree = create_bitree(&mut vnodes);
    println!("搜索二叉树：{:?}", tree.is_bts());
    println!("平衡二叉树：{:?}", tree.is_bbt());
    println!("完全二叉树：{:?}", tree.is_cbt());
    println!("满二叉树：{:?}", tree.is_fbt());
    println!("满二叉树[递归]：{:?}", tree.is_fbt_cursive());

    let tree = "5_1_N_3_2_N_N_4_N_N_9_7_6_N_N_8_N_N_N";
    println!("\ntree: {:?}", tree);
    let mut vnodes: VecDeque<&str> = tree.split("_").collect();
    let tree = create_bitree(&mut vnodes);
    println!("搜索二叉树：{:?}", tree.is_bts());
    println!("平衡二叉树：{:?}", tree.is_bbt());
    println!("完全二叉树：{:?}", tree.is_cbt());
    println!("满二叉树：{:?}", tree.is_fbt());
    println!("满二叉树[递归]：{:?}", tree.is_fbt_cursive());
    let n1 = find_node(&tree, 8);
    let n2 = find_node(&tree, 9);
    let node = find_lca(&tree, &n1, &n2);
    println!("\n{}, {}的共同父节点：{}", n1, n2, node);
    let node = find_lca_cursive(&tree, &n1, &n2);
    println!("{}, {}的共同父节点[递归]：{}", n1, n2, node);
    let n1 = find_node(&tree, 8);
    let n2 = find_node(&tree, 6);
    let node = find_lca(&tree, &n1, &n2);
    println!("{}, {}的共同父节点：{}", n1, n2, node);
    let node = find_lca_cursive(&tree, &n1, &n2);
    println!("{}, {}的共同父节点[递归]：{}", n1, n2, node);
    let n1 = find_node(&tree, 8);
    let n2 = find_node(&tree, 3);
    let node = find_lca(&tree, &n1, &n2);
    println!("{}, {}的共同父节点：{}", n1, n2, node);
    let node = find_lca_cursive(&tree, &n1, &n2);
    println!("{}, {}的共同父节点[递归]：{}", n1, n2, node);

    let tree = "5_1_N_3_2_N_N_4_N_N_9_7_6_N_N_8_N_N_N";
    println!("\ntree: {:?}", tree);
    let mut vnodes: VecDeque<&str> = tree.split("_").collect();
    let tree = create_node3tree(&mut vnodes, &Node3Link(None));
    println!("中序遍历：");
    Node3Link::midorder_cursive(&tree);
    println!("先序遍历：");
    Node3Link::preorder_cursive(&tree);

    for i in 0..10 {
        let node = Node3Link::find_node3(&tree, i);
        let successor = tree.find_node_successor(&node);
        println!("{}的后继节点：{}", node, successor);
    }

    println!("\n======== morris 遍历 ==========");
    let tree = "5_1_N_3_2_N_N_4_N_N_9_7_6_N_N_8_N_N_N";
    println!("\ntree: {:?}", tree);
    let mut vnodes: VecDeque<&str> = tree.split("_").collect();
    let tree = create_bitree(&mut vnodes);
    morris_pre(&tree);
    morris_mid(&tree);
    morris_post(&tree);

    let tree = "1_2_4_N_N_5_N_N_3_6_N_N_7_N_N";
    println!("\ntree: {:?}", tree);
    let mut vnodes: VecDeque<&str> = tree.split("_").collect();
    let tree = create_bitree(&mut vnodes);
    morris_pre(&tree);
    morris_mid(&tree);
    morris_post(&tree);
}
